package com.lzq.leetcode;

import java.util.Arrays;

public class s300 {
    public static int lengthOfLIS(int[] nums) {

        int len = nums.length;
        int []minFlor = new int[len];
        int maxLen = 1;
        minFlor[0] = nums[0];
        for (int i=1; i<len; i++) {
            if (nums[i] > minFlor[maxLen-1]) {
                minFlor[maxLen++] = nums[i];
            } else {
                // 二分查找
                int left = 0;
                int right = maxLen;
                int pos = -1;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[i] < minFlor[mid]) {
                        pos = mid;
                        right = mid - 1;
                    } else if (minFlor[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        pos = mid;
                        break;
                    }
                }
                if (pos != -1)  minFlor[pos] = nums[i];
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{4,10,4,3,8,9}));
    }
}
